1. Field of the Invention
The present invention relates to a system for (1) protecting the transmission of (live data) packet streams between a host computer and one or more client computers, and (2) upon reception, (a) reconstructing any outage damage caused during the transmission to the packet streams, and (b) digitally recording the reconstructed packet streams to a file. The present invention also relates to a method for dynamically generating a file index table as the packet stream is being digitally recorded.
2. Description of Related Art
U.S. Pat. No. 6,012,159, which is incorporated herein by reference, discloses a forward error correction (FEC) encoding method for reliably transferring packets of data between a transmitter and receiver in a computer network or communication system. In particular, that patent provides various packet-level FEC encoding techniques to ensure that large, multimedia data files, including digitized music, still images or moving images, such as may be transmitted by a host computer to one or more receiver subscriber computers using one-way satellite broadcasting, are received error free despite the effects of various types of noise interfering with the transmitted signal.
In many computer networks or communication systems, including the aforementioned one-way satellite broadcast system, the data bits or symbols (such as octets or bytes) are organized into larger groups called packets. When a file is transmitted, uncoded header packets preceding the information-containing packets are sent. Those header packets contain the address and control information to ensure that the following information packets are received by the addressed subscriber computers. Moreover, each packet itself includes uncoded header bytes that indicate, inter alia, to which file the packet belongs and the position of the packet within that file. The remaining bytes of the packet are the body which includes the informational data, such as compressed video data. For example, a packet may be 4,096 bytes long, wherein the header portion is the first 16 bytes, and the body portion is the remaining 4,080 bytes. A large digital object is thus transmitted as a sequence of “original” or “source” packets.
In the techniques described in U.S. Pat. No. 6,012,159, an extra number of error correcting “wildcard” packets are encoded and transmitted with the original packets to provide a predetermined level of protection against packet loss. For example, if a file contains 180 original packets, an extra 20 wildcard packets may be encoded and transmitted with those 180 original packets, as shown in FIG. 1A, to protect against a loss of any 20 packets (a 10% loss of the total transmitted). For the reasons described in that patent, the addressed subscriber computers can successfully reconstruct the large digital object from the received packets so long as any 180 packets, of the 200 packets transmitted, are successfully received.
Additionally, as also described in U.S. Pat. No. 6,012,159, a large file may be broken into smaller “chunks” or “shares”, each of which generally contains the same number of packets, to allow the large file to be more easily transmitted and received by the system. Each share is individually encoded, transmitted, received and reconstructed (decoded). The file is made whole from the individually constructed shares. As also discussed in that patent, the packets of the shares may be interleaved to provide additionally protection against the effects of interfering noise. For example, a data file of 360 original packets and 40 wildcard packets may be divided into two shares of 200 interleaved packets each, as shown in FIG. 1B. Of course, as the files become larger, the number of shares will increase.
As disclosed in U.S. Pat. No. 6,012,159, packet-level error detection processing in the receiving subscriber computers provides an indication that a received packet is “good” or “bad”. Also, an indication is made if a packet has not been received at all, i.e., “lost”. The bad packets are marked as lost and are not used in further decoding. As further explained therein, as long as the number of lost packets does not exceed the number of wildcard packets, the original packets of the file or share may be completely and correctly reconstructed. Continuing the above examples, for each file or share, at least 180 packets of the 200 transmitted packets must be received as “good” packets for the successful reconstruction of the original 180 packets. The techniques for decoding the received good packets to reconstruct the original packets are described more fully in U.S. Pat. No. 6,012,159.
In U.S. Pat. No. 6,272,658, which is also incorporated by reference, the above-described file-oriented packet-level encoding and decoding techniques of U.S. Pat. No. 6,012,159 are extended from data files to data “streams”. In the computer network/communication system arts, a stream may be a continuous sequence of octets (or bytes) without a packet structure, as in the phrase “TCP (transmission control protocol) is a stream-based protocol”. On the other hand, a stream may be a continuous sequence of packets. For example, when those skilled in the art use the phrase “video (or audio) streaming”, they are usually referring to a stream of UDP/IP (user datagram protocol/internet protocol) or IP Multicast packets. For the present application, a stream is generally any data arriving over a period of time which must be processed and transmitted as it arrives, without waiting for the data to end. Usually, the data is generated by an independent source, and at any given point in time the transmitting system has no knowledge of if or when future data will arrive.
In U.S. Pat. No. 6,272,658, data streams are assembled into “virtual files” of packets, and then the file-oriented encoding and decoding techniques of U.S. Pat. No. 6,012,159 are applied thereto. That is, the host computer collects the data of the streams into packets, and the packets are collected into a virtual file. The virtual file is then encoded by the host computer using the techniques of U.S. Pat. No. 6,012,159, and the encoded packets are transmitted to the subscriber computers. At the subscriber computer side, the packets are received and collected into a virtual file, which is then decoded using the techniques of U.S. Pat. No. 6,012,159. Once the virtual file is decoded, it is output by the subscriber as a stream of packets, or as a stream of unpacketized data if applicable. However, the method described in U.S. Pat. No. 6,272,658 has a drawback in that delays are created when the host computer waits for data to arrive from the source so it can be packetized and made into a virtual file. Another delay is created as the subscriber computer waits for the arrival of all of the packets required to reconstruct the virtual file. Further, a great deal of memory, and associated read/write operations, is required for storing the virtual file.
To remove these delays from the “virtual file” method of encoding data streams of U.S. Pat. No. 6,272,658 and to reduce the memory requirements thereof, in U.S. patent application Ser. No. 09/544,161 (which is also incorporated by reference) a method is provided in which the packet-level encoding and decoding techniques of U.S. Pat. No. 6,012,159 are applied directly to data streams without the creation of virtual files. In the method of U.S. patent application Ser. No. 09/544,161, when a packet of data arrives from a source, or a packet is formed from arriving source data bits or octets, the packet's error-correcting contribution to a group of wildcard packets is computed. Once that computation is done, the packet can then be transmitted to the subscriber computer without waiting for the arrival of any other source packet, thus making the encoding process nearly instantaneous. In particular, advantage is taken of the identity submatrix of the encoding generator matrix described in U.S. Pat. No. 6,012,159, which causes the encoded source packets to be identical to the original source packets. Thus no actual encoding of the source packets is required, and the source packets may be transmitted as soon as the computation of its wildcard contributions has been completed. The contributions from the source packets to each wildcard packet of the group are summed, and when all of the contributions have been computed for all of the wildcard packets associated with the group of source packets, the wildcard packets are transmitted. At the receiver, the source packets may be reconstructed from the-received packets using the packet-level decoding techniques set forth in U.S. Pat. No. 6,012,159.
Also in the method of U.S. patent application Ser. No. 09/544,161, if a timeout occurs at the host computer because no further stream data is forthcoming, or a signal is received from the source indicating that the data stream has ended, an appropriate set of wildcard packets is transmitted, thus preventing the data stream information from becoming stale. Optionally, the number of wildcard packets sent, as compared to the total number of wildcard packets normally computed for the group, may be proportional to the number of source packets actually received by the host computer, as compared to the number of source packets normally received by the host computer when no timeout occurs.
As the use of live data streams increases, for example, on the Internet, the need to protect those streams upon transmission with minimal delay and bandwidth, so as to permit perfect reconstruction and recording of the same upon reception, becomes even greater.